class Solution
{
public:
    int orderOfLargestPlusSign(int n, vector<vector<int>> &mines)
    {
        vector<vector<int>> map(n, vector<int>(n, 1));
        for (auto &mine : mines)
        {
            map[mine[0]][mine[1]] = 0;
        }
        vector<vector<int>> result(n, vector<int>(n, n));
        auto maxExtendDp(map);
        for (int i = 0; i < n; ++i)
        {
            result[i][0] = maxExtendDp[i][0] = (map[i][0] != 0);
            for (int j = 1; j < n; ++j)
            {
                if (map[i][j] == 0)
                {
                    maxExtendDp[i][j] = 0;
                }
                else
                {
                    maxExtendDp[i][j] = maxExtendDp[i][j - 1] + 1;
                }
                result[i][j] = min(result[i][j], maxExtendDp[i][j]);
            }
        }
        for (int i = 0; i < n; ++i)
        {
            result[i][n - 1] = maxExtendDp[i][n - 1] = (map[i][n - 1] != 0);
            for (int j = n - 2; j >= 0; --j)
            {
                if (map[i][j] == 0)
                {
                    maxExtendDp[i][j] = 0;
                }
                else
                {
                    maxExtendDp[i][j] = maxExtendDp[i][j + 1] + 1;
                }
                result[i][j] = min(result[i][j], maxExtendDp[i][j]);
            }
        }
        for (int i = 0; i < n; ++i)
        {
            result[0][i] = maxExtendDp[0][i] = (map[0][i] != 0);
            for (int j = 1; j < n; ++j)
            {
                if (map[j][i] == 0)
                {
                    maxExtendDp[j][i] = 0;
                }
                else
                {
                    maxExtendDp[j][i] = maxExtendDp[j - 1][i] + 1;
                }
                result[j][i] = min(result[j][i], maxExtendDp[j][i]);
            }
        }
        for (int i = 0; i < n; ++i)
        {
            result[n - 1][i] = maxExtendDp[n - 1][i] = (map[n - 1][i] != 0);
            for (int j = n - 2; j >= 0; --j)
            {
                if (map[j][i] == 0)
                {
                    maxExtendDp[j][i] = 0;
                }
                else
                {
                    maxExtendDp[j][i] = maxExtendDp[j + 1][i] + 1;
                }
                result[j][i] = min(result[j][i], maxExtendDp[j][i]);
            }
        }
        int largest = 0;
        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                largest = max(largest, result[i][j]);
            }
        }
        return largest;
    }
};